#!/usr/bin/env python3

"""
Given a string s, and a list of words that are all of the same length. Find all starting
indices of substring(s) in s that is a concatenation of each word in words exactly once and 
without any intervening characters
"""

import copy

class Solution:
    def find_substring(self, s, words):
        if len(words) == 0:
            return []
        window_size = len(words[0])
        start = 0
        end = start + window_size * len(words)
        words_map = {}
        for word in words:
            if word in words_map:
                words_map[word] += 1
            else:
                words_map[word] = 1

        result = []
        while end <= len(s):
            if self.is_valid_win(s, words_map, start, end, window_size):
                result.append(start)
            start += 1
            end = start + window_size * len(words)
        return result

    def is_valid_win(self, s, words_map, start, end, window_size):
        words_map = copy.copy(words_map)
        inner_start = start
        inner_end = start + window_size
        while inner_end <= end:
            window = s[inner_start:inner_end]
            if window in words_map:
                if words_map[window] == 1:
                    del words_map[window]
                else:
                    words_map[window] -= 1
                inner_start = inner_end
                inner_end += window_size
            else:
                return False
        return True

if __name__ == '__main__':
    solution = Solution()
    result = solution.find_substring("barfoofoobarthefoobarman", ["bar","foo","the"])
    print(str(result))
